package cn.felord.boot;
import java.util.concurrent.atomic.AtomicReference;
public class ThreadSafeQueue<T> {

    // 定义队列节点
    private static class Node<T> {
        T value;
        AtomicReference<Node<T>> next;

        Node(T value) {
            this.value = value;
            this.next = new AtomicReference<>(null);
        }
    }

    // 队列的头节点和尾节点
    private final AtomicReference<Node<T>> head;
    private final AtomicReference<Node<T>> tail;

    public ThreadSafeQueue() {
        Node<T> dummy = new Node<>(null); // 哨兵节点
        this.head = new AtomicReference<>(dummy);
        this.tail = new AtomicReference<>(dummy);
    }

    // 入队操作
    public void enqueue(T value) {
        Node<T> newNode = new Node<>(value);
        while (true) {
            Node<T> currentTail = tail.get();
            Node<T> tailNext = currentTail.next.get();

            if (currentTail == tail.get()) { // 检查是否被其他线程修改
                if (tailNext != null) {
                    // 有其他线程正在插入，帮助推进尾节点
                    tail.compareAndSet(currentTail, tailNext);
                } else {
                    // 尝试插入新节点
                    if (currentTail.next.compareAndSet(null, newNode)) {
                        // 插入成功，尝试推进尾节点
                        tail.compareAndSet(currentTail, newNode);
                        return;
                    }
                }
            }
        }
    }

    // 出队操作
    public T dequeue() {
        while (true) {
            Node<T> currentHead = head.get();
            Node<T> currentTail = tail.get();
            Node<T> headNext = currentHead.next.get();

            if (currentHead == head.get()) { // 检查是否被其他线程修改
                if (currentHead == currentTail) {
                    if (headNext == null) {
                        // 队列为空
                        return null;
                    }
                    // 有其他线程正在插入，帮助推进尾节点
                    tail.compareAndSet(currentTail, headNext);
                } else {
                    // 尝试移除头节点
                    T value = headNext.value;
                    if (head.compareAndSet(currentHead, headNext)) {
                        return value;
                    }
                }
            }
        }
    }

    // 测试代码
    public static void main(String[] args) {
        ThreadSafeQueue<Integer> queue = new ThreadSafeQueue<>();

        // 生产者线程
        Thread producer = new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                queue.enqueue(i);
                System.out.println("Enqueued: " + i);
            }
        });

        // 消费者线程
        Thread consumer = new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                Integer value = queue.dequeue();
                System.out.println("Dequeued: " + value);
            }
        });

        producer.start();
        consumer.start();

        try {
            producer.join();
            consumer.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}